트리(Тree)는 비선형적인 계층적 데이터 구조로, 파일 시스템이나 가계도와 같은 현실 세계의 조직 구조를 모방합니다. 리스트, 스택, 큐와 같은 선형 배열과 달리, 트리의 본질은 그계층성 (계층적)그리고재귀성 (재귀적)입니다.
1. 트리의 형태 분석하기
- 노드 (노드): 키(Key)와 유효 데이터를 포함하는 기본 단위입니다.
- 루트 노드 (루트): 유일하게 들어오는 간선이 없는 노드이며, 트리의 시작점입니다.
- 간선 (간선): 노드를 연결하는 유일한 경로로, 부모-자식 관계를 나타냅니다.
- 잎 노드 (잎): 자식 노드가 없는 끝단으로, 재귀 종료의 자연스러운 경계입니다.
2. 재귀적 정의의 이중 시각
트리를 이해하는 데에는 두 가지 시각이 있습니다:
도형학적 시각
由节点和边构成的无环、连通图，每个节点（除根外）有且仅有一个父节点。
由节点和边构成的无环、连通图，每个节点（除根外）有且仅有一个父节点。
재귀적 시각
트리는 공백이거나, 하나의 루트 노드와 0개 이상의 서브트리(Subtree)로 구성됩니다.
트리는 공백이거나, 하나의 루트 노드와 0개 이상의 서브트리(Subtree)로 구성됩니다.
HTML DOM 트리 예제
HTML에서,
<html> 는 루트이며,<body> 그리고 <head> 는 형제 노드입니다. 각 태그와 중첩된 내용은 함께 하나의 서브트리를 형성합니다. 이러한 구조 덕분에 우리는 <ul>을 전체적으로 이동시킬 수 있으며, 내부 계층 구조를 파괴하지 않습니다. <ul> 그리고 모든 <li> 내부 계층 구조를 파괴하지 않고요.